#include<bits/stdc++.h>
using namespace std;
int T,n,a[100005],f[2020][2][2020],pre[100005],id[100005];//dp pos now_color pos_of_other color
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        memset(a,0,sizeof a);
    memset(f,0,sizeof f);
    memset(pre,0,sizeof pre);
    memset(id,0,sizeof id);
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            pre[i] = id[a[i]];
            id[a[i]] = i;
        }
        for(int i=2;i<=n;i++){
            for(int j=0;j<=1;j++){
                int ret2 = 0;
                if(a[i-1]==a[i])ret2 = a[i];
                for(int k=0;k<=i-2;k++){
                    int ret1 = 0;
                    if(a[k]==a[i])ret1 = a[i];
                    f[i][j][i-1] = max(f[i][j][i-1],f[i-1][j^1][k]+ret1);
                    f[i][j][k] = f[i-1][j][k] + ret2;
                    //printf("%d %d %d %d\n",i,j,k,f[i][j][k]);
                }
                //printf("%d %d %d %d\n",i,j,i-1,f[i][j][i-1]);
            }
        }
        int ans = 0;
        for(int i=0;i<=1;i++){
            for(int k=0;k<=n-1;k++){
                ans = max(ans,f[n][i][k]);
                //printf("%d %d %d\n",i,k,f[n][i][k]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
